1. Field of the Invention
The present invention generally relates to the art of computerized computation as applied to the control of a process such as real-time control of a robot or other autonomous agent. The present invention relates also to the art of computerized learning systems (which are usually characterized by the need to perform repeated computations on run-time data) and more specifically to a register machine learning method in which the information and/or the computer program(s) that constitute solutions to a problem are created, initialized, stored, altered and executed in native machine code by using a higher level programming language to produce an optimized solution through the direct application of learning algorithms to the information stored in the native machine code.
In a preferred form of the invention, a computerized computation system performs repeated computations on data that is not known until a computer user is running tyhe system ("run-time", and "run-time data") and more specifically creates, intializes, stores, alters and executes both the run-time data and the computer code necessary to execute the repeated computations (the "related code") in native machine code operating on a register machine.
2. Description of the Related Art
The use of an evolutionary method to evolve controller architectures has been reported previously in a number of variants. Robotic controllers have, for instance, been evolved using dynamic recurrent neural nets. Several experiments have also been performed where a controller program has been evolved directly through genetic programming.
Previous experiments with genetic programming and robotic control, however, have been performed with a simulated robot and a simulated environment. In such a set-up, the environment and the robot can be reset easily to an initial state in order to ensure that each individual in the population is judged starting from the same state. Apart from being practically infeasible for a real robot, this method could result in over-specialization and failure to evolve a behavior that can generalize to unseen environments and tasks. To overcome the latter problem noise is sometimes artificially added to the simulated environment.
Machine learning systems in general have been proposed in the art for the solution of problems such as classification, prediction of time-series data, symbolic regression, optimal control, etc. Examples of various machine learning systems are neural networks, fuzzy networks, genetic algorithms (including genetic programming and classifier systems), Evolutionary Strategies, Evolutionary Programming, ADATE program induction, cellular automata, Box Jenkins optimization, ARMA optimization and many others. Rather than applying a direct computational approach, these systems create one or more proposed solutions in the form of data and computer program entities, and iteratively alter the data and/or entities for the purpose of finding an optimal solution to a problem. One such approach is described in, for example, U.S. Pat. No. 4,935,877, entitled "NON-LINEAR GENETIC ALGORITHMS FOR SOLVING PROBLEMS", issued Jun. 19, 1990 to John Koza.
The set of practically solvable problems is highly related to the efficiency of the algorithm and implementation. It is therefore important to minimize the overhead involved in executing any machine learning system.
Machine learning systems create learned solutions to problems. These solutions have two elements: (1) Elements that hold the information that is learned during the execution of the machine learning system (the "Learned Elements"); and (2) Elements that are necessary to convert the Learned Elements into meaningful action or output by the computer (the "Conversion Elements"). Existing machine learning approaches other than the present invention can be classified into two categories in terms of how they store and execute both the Learned Elements and the Conversion Elements. Those two categories are compiler based systems and interpreted systems.
An interpreted system is written in a high level language such as LISP and both the Learned and Conversion Elements are held in data-like structures such as LISP lists, which are converted ("interpreted") into native machine code at run-time by an interpreter. The interpreter, itself, also contains Conversion Elements for such interpreted systems. So for example, U.S. Pat. No. 4,935,877 uses, as its Learning Elements various high level LISP expressions, customized for the problem at hand, to represent, symbolically, a "computer program." That is, a high level "program" structure symbolized by the LISP List, is itself the subject of learning in that system. In this system, the Learned Elements are represented as a hierarchical tree structure. This solution gives good flexibility and the ability to customize the language depending on the constraints of the problem at hand.
The principal disadvantage of this interpreting approach to machine learning is that the Learned Elements and many of the Conversion Elements are stored in high level, symbolic data-like structures. Computers can operate only by executing native machine code. Thus, interpreting machine learning systems learn by modifying high level symbolic representations (the Learned Elements) that are, ultimately, converted into machine code by the interpreter at run-time. The need to convert (interpret) the Learned Elements and some of the Conversion Elements into native machine code at run-time before any useful action or output may be had from a computer is very time consuming and involves a large amount of overhead in machine resources such as CPU time, RAM memory, and disk space. In effect, all of the Learned Elements and the Conversion Elements in the LISP List are treated as run-time data that must be accessed and converted to machine code before any useful action or output may be had. Simply put, interpreted systems are slow and use a lot of a computer system's resources.
Other machine learning systems are written in high level compiled computer languages such a C, C++, Pascal and so forth. This is the "compiler based" approach to machine learning. Large amounts of the Conversion Elements in such systems are compiled before run-time into native machine code in such a compiler based approach. Because those compiled Conversion Elements are already in native machine code at run-time, there is no need to interpret these Conversion Elements at run-time. Using a compiler based approach instead of an interpreted approach usually results in a substantial speed-up of the execution of the machine learning system, often increasing the speed of learning by a factor of ten times. Examples of such compiler based systems are GPC by Walter Tackett (genetic programming), Lil-GP (genetic programming), and EvoC (evolutionary strategies).
The compiler based approach to machine learning, while faster than the interpreted approach, must still access run-time data that is stored in data structures held in RAM memory or in some other form of memory such as hard disk. The reason that run-time data structures must be accessed in compiler based machine learning systems (or any machine learning system other than the present invention) is that the process of learning involves initializing and then altering the Learned Elements at run-time.
For example, the weights in a neural network are Learned Elements for neural network applications. Compiler based neural network systems hold those weights in data structures such as arrays or linked lists. Similarly, compiler based genetic programming systems store symbolic representations of program structures (the Learned Elements in genetic programming) in RAM data structures such as arrays, linked lists or parse trees. In all compiler based machine learning systems, the already compiled Conversion Elements must repeatedly access the Learned Elements (weights or symbolic representations of program structures) from the data structures in RAM memory in order to execute and evaluate the Learned Elements and to modify the Learned Elements according to the learning algorithm that is being used to modify the Learned Elements during learning. Such repeated access is necessary before any meaningful output or action may be had from a computer based on the Learned Elements. Such repeated accesses to RAM data structures is time consuming and uses extensive amounts of RAM to hold the Learned Elements.
More generally, computing systems that perform repeated calculations on run-time data may also be categorized as compiler based systems or interpreted systems. They store access, alter and execute run-time data in a manner similar to the storage, access, alteration and execution of the Learned Elements in the systems described above and are subject to the same limitations of slow execution and system overhead as the systems described above. By the phrase, "repeated calculations (or computations) on (or of) run-time data," this application means the execution of one or more instructions that must access one or more elements of run-time data (from data storage such as RAM or hard disk) more than once on the same values of the run-time data.